package BackTrackingPackage3;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class permuteUnique_ {
  List<List<Integer>> result = new ArrayList<>();
  List<Integer> path = new ArrayList<>();

  @Test
  public void permuteUniqueTest(){
    int[] nums = new int[]{1,1,2};
    List<List<Integer>> lists = permuteUnique(nums);
    for (List<Integer> list : lists) {
      System.out.println(list.toString());
    }
  }

  public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    boolean[] used = new boolean[nums.length];
    Arrays.fill(used,false);
    backTracking(nums,used);
    return result;
  }
  public void backTracking(int[] nums,boolean[] used){
    if (path.size() == nums.length){
      result.add(new ArrayList<>(path));
      return;
    }
    for (int i = 0 ; i < nums.length ; i++){
      if (i > 0 && nums[i] == nums[i- 1] && !used[i - 1]){
        continue;
      }
      else{
        if (used[i] == false){
          used[i] = true;
          path.add(nums[i]);
          backTracking(nums,used);
          path.remove(path.size() - 1);
          used[i] = false;
        }
      }
    }
  }
}
